package dp;

public class _17_322_零钱兑换 {

    public static int coinChange(int[] coins, int amount) {
    	int dp[] = new int[amount+1];
    	// 当amount = 0. dp[0] = 0
    	dp[0] = 0;
    	for(int i = 1; i <= amount; i++) {
    		dp[i] = Integer.MAX_VALUE;
    	}
    	// 题意要求的是凑成总金额所需的最少的硬币个数，所以物品和背包的遍历顺序先后都可以
    	for(int i = 0; i < coins.length; i++) {
    		// 正序遍历，完全背包每个硬币可以选择多次
    		for(int j = coins[i]; j <= amount; j++) {
    			// 只有dp[j-coins[i]]不是初始的最大值时，该位才有选择的必要，
    			// 否则如果 MAX_VALUE + 1 会变成 MIN_VALUE：:-2147483648
    			if(dp[j - coins[i]] != Integer.MAX_VALUE) {
    				dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
    			}
    		}
    	}

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];

    }
	
	public static void main(String[] args) {
		int[] coins = {186,419,83,408};
		System.out.println(coinChange(coins, 6249));
	}
}
